package graph;

import java.util.Iterator;
import java.util.List;
import java.util.Vector;

/**
 *
 * @author Roberto Maestre Martínez <roberto.maestre AT cchs.csic.es>
 */
public class Undirectgraph extends Graph {

    /**
    * * @param  Structure used to Floyd Algorithm
    */
   private int[][] cm;

   /**
    * * @param  Structure used to Floyd Algorithm
    */
   private int[][] caminos;


   /**
    * * @param  Structure used to get center nodes
    */
   List<Integer>[] component;


   /**
    * Add edge between tow nodes of the graph with weight
    *
    * @param x Colum of matrix
    * @param y Row of matrix
    * @param weigth Weight for the edge
    * @param label Label for the edge
    */
   public void addEdge(int x,int y,int weigth) throws Exception{
        m[x][y]=weigth;
        //Add inverse edge
         m[y][x]=weigth;
   }



   /**
    * Floyds Algorithm
    *
    */
   public void floyd() throws Exception{
        int i,j,k;
        //Create aux structures
        cm = new int[N][N];
        caminos = new int[N][N];
        //Init aux structures
        for(i=1;i<N;i++)
            for(j=1;j<N;j++){
                cm[i][j]=m[i][j];
                if (m[i][j]!=INF) caminos[i][j]=i;
                else caminos[i][j]=INF;
            }
        //Eliminate bucles
        for(i=1;i<N;i++){
            cm[i][i]=0;
            caminos[i][i]=0;
        }
        //Go floyd
        for(k=1;k<N;k++) {
            for(i=1;i<N;i++)
                if ((i!=k) && (getCm()[i][k]!=INF))
                    for(j=1;j<N;j++)
                        if ((k!=j) && (getCm()[k][j]!=INF) && ((getCm()[i][k]+getCm()[k][j])<getCm()[i][j])) {
                            cm[i][j]=getCm()[i][k]+getCm()[k][j];
                            caminos[i][j]=k;
                        }
        }
    }


   /**
    * Provide command line output of floyd paths
    *
    */
   public void systemOutPrintPaths() throws Exception{
        systemOutPrintGeneralMatrix(getCaminos());
   }


   
   /**
    * Provide command line output of floyd costs
    *
    */
   public void systemOutPrintPathCostsMatrix() throws Exception{
        systemOutPrintGeneralMatrix(getCm());
   }

   

   /**
    * If exists, get route between two nodes, id doesn´t exist, return null vector
    *
    * @return  List<Integer> Route nodes
    */
   public PathCost getPathAndCostBetweenNodes(int start,int end){
       List<Integer> lPathHead=null;
       List<Integer> lPathTail=null;
       List<Integer>  lPathInvHead=null;
       List<Integer>  lPathInvTail=null;
       PathCost pathcost = null;
       if (getCm()[start][end]==INF)
           return pathcost;
       else {
           pathcost = new PathCost();
           lPathHead=new Vector();
           lPathTail=new Vector();
           lPathInvHead=new Vector();
           lPathInvTail=new Vector();
           //First search in head route
           int nDinamic=end;
           int c=1;
           while(start!=getCaminos()[start][nDinamic] && getCaminos()[start][nDinamic]!=0){
               nDinamic=getCaminos()[start][nDinamic];
               lPathHead.add(nDinamic);
               lPathInvHead.add(-1);
               c++;
           }
           lPathInvHead.add(-1);
           lPathHead.add(start);
           int halfNode=lPathHead.get(0);
           //Second search in head route
           lPathTail=new Vector();
           c=1;
           while(halfNode!=getCaminos()[halfNode][end] && getCaminos()[halfNode][end]!=0){
               halfNode=getCaminos()[halfNode][end];
               lPathTail.add(halfNode);
               lPathInvTail.add(-1);
               c++;
           }
           //Add end node
           lPathInvTail.add(-1);
           lPathTail.add(end);
       }
        int cont=0;
        for (int i=lPathHead.size()-1;i>=0;i--) {
            lPathInvHead.set(i, lPathHead.get(cont));
            cont++;
        }
        for (int i=0;i<lPathTail.size();i++) {
            lPathInvHead.add(lPathTail.get(i));
            cont++;
        }
       pathcost.setPath(lPathInvHead);
       pathcost.setCost(getCm()[start][end]);
       return pathcost;
   }



    public String toGraphviz() throws Exception {
       String string="graph Grafo{ ";
       for (int i=1;i<N;i++)
           for (int j=i;j<N;j++)
               if (m[i][j]!=INF)
                    string+=i+"--"+j+" [label=\""+this.getEdgeWeight(i, j)+"\"];";
       //Get nodes without conexion
       boolean connect;
       for (int i=1;i<N;i++) {
           connect=false;
           int j=1;
           while (j<N && !connect) {
               if (m[i][j]!=INF) connect=true;
               j++;
           }
           if (!connect) string+=i+";";
       }
       string+="}";
       return string;
    }


    /**
     * @return the minimun costs between nodes
     */
    public int[][] getCm() {
        return cm;
    }


    /**
     * @return the paths of floyd paths matrix
     */
    public int[][] getCaminos() {
        return caminos;
    }


    /**
     * Return the max value of integer array. Use Divide and conqueror techniq.
     *
     * @param m array of values
     * @param i inf position
     * @param s sup position
     *
     * @return the max value in array
     */
    private int dac(int[] m, int i, int s) {
        if (s-i==0) {
            return m[i];
        }
        else if (s-i==1) {
            if (m[s]>m[i]) return m[s];
            else return m[i];
        } else {
            int h=((s-i) / 2)+i;
            int a = dac(m,i,h);
            int b = dac(m,h+1,s);
            if (a>b) return a;
            else return b;
        }
    }


     /**
     * Return the max value of integer array. Use Divide and conqueror techniq.
     *
     * @param m array of values
     * @param i inf position
     * @param s sup position
     *
     * @return the min value in array
     */
    private int dacLowValue(int[] m, int i, int s) {
        if (s-i==0) {
            return m[i];
        }
        else if (s-i==1) {
            if (m[s]<m[i]) return m[s];
            else return m[i];
        } else {
            int h=((s-i) / 2)+i;
            int a = dacLowValue(m,i,h);
            int b = dacLowValue(m,h+1,s);
            if (a<b) return a;
            else return b;
        }
    }


    /**
     * Graph breadth search saving the expansion value
     *
     * @param node Node for start de breadth search
     *
     * @return int the breadth of the graph starting for one node
     */
    private int deep(int node){
        int[] expansionNode = new int[N];
        for (int j=1;j<N;j++) { visits[j]=false; expansionNode[j]=0;}
        List<Integer> cola = new Vector();
        cola.add(node);
        while (cola.size()>0) {
            node = cola.get(0); cola.remove(0);
            visits[node]=true;
                for (int a=1;a<N;a++)
                    if (m[node][a]!=INF && !visits[a] && a!=node) {
                        cola.add(a);
                        visits[a]=true;
                        expansionNode[a]=expansionNode[node]+1;
                    }
        }
        return dac(expansionNode,1,expansionNode.length-1);
    }



    private boolean exists(List<Integer> l,int k) {
        boolean res=false;
        Iterator i = l.iterator();
        while (i.hasNext() && !res)
            if ((Integer) i.next()==k) res=true;
        return res;
    }



    private void deepInComponents(){
        int[] expansionNode = new int[N];
        List<Integer>[] componentAux = new List[N+1];
        visits = new boolean[N];
        for (int j=1;j<N;j++) { visits[j]=false; expansionNode[j]=0;}
        List<Integer> cola = new Vector();
        int componentCont=1;
        componentAux[componentCont]=new Vector();
        for (int nodeIterator=1;nodeIterator<N;nodeIterator++) {
            boolean nodeInOtherComponente=false;
            int cont=1;
            while (cont<componentCont && !nodeInOtherComponente) {
                if (exists(componentAux[cont],nodeIterator)) nodeInOtherComponente=true;
                cont++;
            }
            if (!nodeInOtherComponente) {
              cola.add(nodeIterator);
              componentAux[componentCont].add(nodeIterator);
              while (cola.size()>0) {
                  int node = cola.get(0); cola.remove(0);
                  visits[node]=true;
                      for (int a=1;a<N;a++)
                          if (m[node][a]!=INF && !visits[a] && a!=node) {
                              componentAux[componentCont].add(a);
                              cola.add(a);
                              visits[a]=true;
                              expansionNode[a]=expansionNode[node]+1;
                          }
              }
              componentCont++;
              componentAux[componentCont]=new Vector();
            }
        }
        //Generate componente vector
        this.component = new List[componentCont];
        for (int c=1;c<componentCont;c++)
            component[c] = componentAux[c];
    }




     public List<Integer> getCenterNodesOfAcomponent(int component){
        List<Integer> result = new Vector();
        visits = new boolean[N];
        int[] centerNodes = new int[N];
        this.deepInComponents();
        Iterator it = this.component[component].iterator();
        int cont=1;
        while(it.hasNext()) {
            auxInt=0;
            centerNodes[cont]=deep((Integer) it.next());
            cont++;
        }
        int lowValue=dacLowValue(centerNodes,1,cont-1);
        it = this.component[component].iterator();
        cont=1;
        while(it.hasNext()) {
            int i = (Integer) it.next();
            if (centerNodes[cont]==lowValue)
                result.add(i);
            cont++;
        }
        return result;
    }




    /**
     * Return a list of nodes. These nodes are the center of the graph.
     *
     * @return int the breadth of the graph starting for one node
     */
    public List<Integer> getCenterNodes(){
        List<Integer> result = new Vector();
        visits = new boolean[N];
        this.deepInComponents();
        int components = component.length;
        for (int i=1;i<components;i++) {
            auxInt=0;
              List<Integer> aux = this.getCenterNodesOfAcomponent(i);
            Iterator it = aux.iterator();
            while(it.hasNext())
                result.add((Integer) it.next());
        }
        return result;
    }



}
